#include <bits/stdc++.h>
using namespace std;

/*
3147. 从魔法师身上吸取的最大能量
已解答
中等
相关标签
premium lock icon
相关企业
提示
在神秘的地牢中，n 个魔法师站成一排。每个魔法师都拥有一个属性，这个属性可以给你提供能量。有些魔法师可能会给你负能量，即从你身上吸取能量。

你被施加了一种诅咒，当你从魔法师 i 处吸收能量后，你将被立即传送到魔法师 (i + k) 处。这一过程将重复进行，直到你到达一个不存在 (i + k) 的魔法师为止。

换句话说，你将选择一个起点，然后以 k 为间隔跳跃，直到到达魔法师序列的末端，在过程中吸收所有的能量。

给定一个数组 energy 和一个整数k，返回你能获得的 最大 能量。

 

示例 1：

输入： energy = [5,2,-10,-5,1], k = 3

输出： 3

解释：可以从魔法师 1 开始，吸收能量 2 + 1 = 3。

示例 2：

输入： energy = [-2,-3,-1], k = 2

输出： -1

解释：可以从魔法师 2 开始，吸收能量 -1。

 

提示：

1 <= energy.length <= 105
-1000 <= energy[i] <= 1000
1 <= k <= energy.length - 1
 
*/

// 法一
class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
        // 直接来 要超时  就取模  减少遍历次数
        int n = energy.size();
        int max_energy = INT_MIN;  // 全局最大能量

        // 按「i mod k」分组，共k组（0~k-1），每组内元素间隔为k
        for (int mod = 0; mod < k; ++mod) {
            int current_suffix_sum = 0;  // 组内当前后缀和（从后往前累加）
            // 从组内最后一个元素开始，往前遍历所有组内元素（每次跳k步）
            // 组内元素为：mod, mod+k, mod+2k, ..., 最后一个 <=n-1 的元素
            for (int j = n - 1 - (n - 1 - mod) % k; j >= mod; j -= k) {
                current_suffix_sum += energy[j];  // 累加当前元素，得到从j开始的序列和
                max_energy = max(max_energy, current_suffix_sum);  // 更新全局最大值
            }
        }
        return max_energy;
    }
};

// 法二
static const auto ______ = []() {std::ios::sync_with_stdio(false); std::cin.tie(nullptr); return 0; }();

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) 
    {
        // 从后往前遍历，累加后续k步的能量和
        // 每个位置i最终存储：以i为起点，每次跳k步的所有能量总和
        for (int i = energy.size() - 1; i - k >= 0; i--)
        {
            energy[i - k] += energy[i];  // i-k位置的序列和 = 自身能量 + i位置的序列和（i是i-k跳k步后的位置）
        }

        // 数组中最大值即为所有可能起点的最大能量和
        return *max_element(energy.begin(), energy.end());
    }
};